{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Longest Increasing Subsequence（最长递增子串）\n",
    "\n",
    "[The Original Question（原题）](https://mp.weixin.qq.com/s/lpVWQm_-u9Q-buiTLCOR6Q)\n",
    "\n",
    "You are given an array of integers. Return the length of the longest increasing subsequence (not necessarily contiguous) in the array. \n",
    "\n",
    "给定一串整数数组，返回给定数组中最长递增子串的长度（值不一定连续）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example（样例）\n",
    "\n",
    "```text\n",
    "Input: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]\n",
    "Output: 6\n",
    "```\n",
    "\n",
    "The longest increasing subsequence is `[0, 2, 6, 9 , 11, 15]`.\n",
    "\n",
    "最长的递增子序列为`[0, 2, 6, 9 , 11, 15]`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solution(array: list) -> int:\n",
    "    ''' Main Algorithm '''\n",
    "    \n",
    "    # Check if the given array is empty.\n",
    "    if array == []:\n",
    "        return 0\n",
    "    \n",
    "    # Create a cache list for Dynamic Programming.\n",
    "    cache = [1] * len(array)\n",
    "    \n",
    "    # Traverse all elements with 2 pointers.\n",
    "    for i in range(len(array)):\n",
    "        for j in range(i):\n",
    "            # If the current element is larger than previous element, ...\n",
    "            if array[i] > array[j]:\n",
    "                # update records.\n",
    "                cache[i] = max(cache[i], cache[j] + 1)\n",
    "    \n",
    "    # Choose the longest one.\n",
    "    return max(cache)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "''' Test Scripts '''\n",
    "print(solution([0, 2, 6, 9 , 11, 15]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tips（提示）\n",
    "\n",
    "This question is a classic *Dynamic Programming* problem. Starting with the first element of the array, the length of the longest increasing subsequence from the header element to the current element is continuously calculated and updated, and finally the longest one is selected.\n",
    "\n",
    "这道题目是一个经典的动态规划问题。从数组头元素开始，不断地计算并更新从数组头元素到当前元素的最长递增子序列长度，最后再选出最长的那个。\n",
    "\n",
    "For the *Dynamic Programming* problem, the difficulty lies in determining the *State Transition Equation*. That is, determining the operator that transitions from the current state to the next state.\n",
    "\n",
    "对于动态规划问题来说，难点在于确定状态转移方程，即确定从当前状态转变为下一状态的算子。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
